package _11_整理题目._3_字符串_递归_dfs_bfs_双指针._排列组合._基本_排列组合数;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 从 n 个元素中取 m 个元素，组成的不同种类
 *
 * 比如 char[] = 0, 1, a, b   k = 2
 * 组合数： 01 0a 0b 1a 1b ab
 * 排列数： 01 0a 0b 1a 1b ab
 *         10 a0 b0 1a b1 ba
 *
 * 对 n 个元素排序后，按照一定的规则选取，避免重复
 * 例如 n = {1, 2, 3, 4}  k =2
 *      0  时可以选取 1 2 3
 *      1  时可以选取 2 3
 *      2  时可以选取 3
 */
public class _020_组合数_Cnm {

    private List<List<Integer>> result = new ArrayList<>();
    private int k;

    public List<List<Integer>> permute(int[] nums, int k) {
        List<Integer> path = new ArrayList<>();
        this.k = k;
        dfs(nums, path, 0);
        return result;
    }

    public void dfs(int[] nums, List<Integer> path, int index) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i=index; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums, path, i+1);
            path.remove(path.size()-1);
        }
    }

    @Test
    public void main() {
        int[] nums = {1, 2, 3, 4};
        List<List<Integer>> res = permute(nums, 2);
        res.forEach(System.out::println);
    }
}
